/*
 * @Author: your name
 * @Date: 2021-10-19 10:01:52
 * @LastEditTime: 2021-10-20 20:44:09
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\动态规划\背包\分组背包\P1757 通天之分组背包\main.cpp
 */
#include<iostream>
#include<algorithm>
using namespace std;

typedef struct{
    int num = 0;
    int a[1010];
    int b[1010];
}obj;

//f[i][j] 前i组 j质量 获得的最大价值
int f[1010][1010];
//ff[i] 前i质量获得的最大价值
int ff[1010];

int main(){
    obj array[120];
    //质量 数目
    int m,n;
    cin >> m >> n;
    //组数目
    int group_num = 0;
    for(int i=1; i<=n; i++){
        int a,b,c;
        cin >> a >> b >> c;
        //去除分组为0的影响
        //c组当前物品数目
        int cnum = array[c].num;
        //统计组数
        if(cnum == 0){
            //c组第一次出现
            group_num++;
            // ver[group_num]++;
            // der[group_num] = c;
            // system("pause");
        }
        //记录当前物品 1开始存储
        cnum++;
        array[c].a[cnum] = a;
        array[c].b[cnum] = b;
        array[c].num = cnum;
    }

    //判断是否输入0组 保证数组从1开始
    if(array[0].num != 0){
        //输入有0组 所有组后移一位
        for(int i=group_num-1; i>=0; i--){
            array[i+1] = array[i];
        }
    }

{
    // 打印
    // for(int i=1; i<=group_num; i++){
    //     int cnum = array[i].num;
    //     for(int j=1; j<=cnum; j++){
    //         cout << array[i].a[j] << " "
    //             << array[i].b[j] << " "
    //             << i << endl;
    //     }
    // }

    // cout << "group_num:" << group_num << endl;
    // for(int i=1; i<=110; i++){
    //     cout << i << " " << ver[i] << " " << der[i] <<endl;
    // }
    // exit(-1);
    //分组
}

    for(int i=1; i<=group_num; i++){
        //遍历分组
        for(int j=m; j>=0; j--){
            //遍历质量
            int cnum = array[i].num;
            for(int k=1; k<=cnum; k++){
                //遍历组内成员

                // //选1 选2 ... 全不选
                // if(j < array[i].a[k]){
                //     //装不下 array
                //     f[i][j] = max(f[i][j],f[i-1][j]);
                // }else{
                //     //装得下
                //     f[i][j] = max(f[i-1][j],f[i][j]);
                //     f[i][j] = max(f[i][j],f[i-1][j-array[i].a[k]]+array[i].b[k]);
                // }

                //化简
                f[i][j] = max(f[i][j],f[i-1][j]);
                if(j >= array[i].a[k]){
                    f[i][j] = max(f[i][j],f[i-1][j-array[i].a[k]]+array[i].b[k]);
                }

                //ff[i]解法
                if(j >= array[i].a[k]){
                    ff[j] = max(ff[j],ff[j-array[i].a[k]]+array[i].b[k]);
                }
            }
        }
    }
    cout << f[group_num][m] << endl;
    cout << ff[m] << endl;
    return 0;
}
